/**
 * UFCG - CEEI - DSC- SI1
 * Projeto da Disciplina Sistema de Informacao 1 - 2011.1
 * 
 * Professor: Hyggo Almeida
 * 
 * Alunos: Felipe de Sousa - felipeso@lcc.ufcg.edu.br
 * 		   Matheus Sampaio - matheusss@lcc.ufcg.edu.br
 *         Henrique Florencio - henriquecf@lcc.ufcg.edu.br
 *         Claudio Cardoso - claudiocaj@lcc.ufcg.edu.br
 * 		   Julio Henrrique - juliohr@lcc.ufcg.edu.br
 * 
 */

package util;

import java.util.List;

public class OrdenadorImpl{


	/**
	 * Metodo que ordena uma dada List passada por parametro
	 * @param vetor - List a ser ordenada;
	 * @return List - lista ordenada
	 */
	public static List<String> ordenaQuickSort(List<String> vetor) {
		if (vetor == null) {
			return null;
		}
		return quickSort(vetor, 0, vetor.size() - 1);
	}

	/**
	 * Metodo privado que executa o quickSort
	 * @param vetor - vetor a ser ordenado
	 * @param inicio - inicio da particao
	 * @param fim - fim da particao
	 * @return List - lista ordenada
	 */
	private static List<String> quickSort(List<String> vetor, int inicio, int fim) {
		if (inicio < fim) {
			int indice = particao(vetor, inicio, fim);
			quickSort(vetor, inicio, indice);
			quickSort(vetor, indice + 1, fim);
		}
		return vetor;
	}

	/**
	 * Metodo que cria a particao utilizada pelo quickSort
	 * @param vetor - vetor a ser ordenado
	 * @param inicio - inicio da particao
	 * @param fim - fim da particao
	 * @return int - indice da particao
	 */
	private static int particao(List<String> vetor, int inicio, int fim) {
		int index = inicio;
		String pivo = (String) vetor.get(index);
		vetor = trocaPosicao(vetor, index, fim);
		for (int i = index = inicio; i < fim; ++i) {
			String palavra = (String) vetor.get(i);
			if (palavra.compareTo(pivo) < 0) {
				vetor = trocaPosicao(vetor, index++, i);
			}
		}
		vetor = trocaPosicao(vetor, index, fim);
		return index;
	}

	/**
	 * Metodo que realiza a troca
	 * @param vetor
	 * @param indice
	 * @param indiceTroca
	 * @return List - a lista parcialmente ordenada
	 */
	private static List<String> trocaPosicao(List<String> vetor, int indice, int indiceTroca) {
		String temp = (String) vetor.get(indice);
		vetor.set(indice,vetor.get(indiceTroca));
		vetor.set(indiceTroca,temp);
		return vetor;
	}

}
